#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/***************************************************************
 *函数名称：help
 *函数功能：输出菜单
 *返回值类型：void
 ****************************************************************/
void help(void) {
    printf("****************************************************************\n");
    printf("*1 ：创建一个线性表      2 ：销毁线性表                        *\n");
    printf("*3 ：清空线性表          4 ：线性表判空                        *\n");
    printf("*5 ：线性表长            6 ：获取元素                          *\n");
    printf("*7 ：查找元素            8 ：获取前驱元素                      *\n");
    printf("*9 ：获取后继元素        10：插入元素                          *\n");
    printf("*11：删除元素            12：遍历线性表                        *\n");
    printf("*13:线性表写文件         14：线性表读文件                      *\n");
    printf("*15：多线性表管理        16：对多线性表进行操作                *\n");
    printf("*17:返回最大子数组和     18：线性表排序                        *\n");
    printf("*19：菜单                0 ：退出                              *\n");
    printf("****************************************************************\n");
}

/***************************************************************
 *函数名称：filehelp
 *函数功能：输出多表的菜单
 *返回值类型：void
 ****************************************************************/
void filehelp(void) {
    printf("1:增加一个线性表\n");
    printf("2:删除一个线性表\n");
    printf("3:查找一个线性表\n");
    printf("4:菜单\n");
    printf("0:退出多线性表管理\n");
}

/***************************************************************
 *函数名称：InitList
 *函数功能： 线性表L不存在，构造一个空的线性表，返回OK，否则返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status InitList(SqList &L) {

    if (L.elem != NULL)
        return INFEASIBLE;                                          //如果线性表存在返回INFEASIBLE
    L.elem = (ElemType *)malloc(sizeof(ElemType) * LIST_INIT_SIZE); //对线性表分配空间
    if (L.elem == NULL) {
        return ERROR; //分配失败返回ERROR
    }
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
    printf("请输入新线性表长度\n");
    scanf("%d", &L.length);
    for (int i = 0; i < L.length; i++) {
        scanf("%d", &L.elem[i]);
    }
    return OK; //创建成功返回OK
}

/***************************************************************
 *函数名称：DestroyList
 *函数功能： 如果线性表L存在，销毁线性表L，释放数据元素的空间，返回OK，否则返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status DestroyList(SqList &L) {
    if (L.elem == NULL)
        return INFEASIBLE; //线性表不存在返回INFEASIBLE
    free(L.elem);          //释放线性表的空间
    L.elem = NULL;         //将线性表指向空指针
    L.length = 0;          //长度清空
    L.listsize = 0;        //最大长度清空
    return OK;             //销毁成功返回OK
}

/***************************************************************
 *函数名称：ClearList
 *函数功能： 如果线性表L存在，删除线性表L中的所有元素，返回OK，否则返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status ClearList(SqList &L) {
    if (L.elem == NULL)
        return INFEASIBLE; //线性表不存在返回INFEASIBLE
    L.length = 0;
    return OK; //清空成功返回OK
}

/***************************************************************
 *函数名称：ListEmpty
 *函数功能： 如果线性表L存在，判断线性表L是否为空，空就返回TRUE，否则返回FALSE；如果线性表L不存在，返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status ListEmpty(SqList L) {
    if (L.elem == NULL)
        return INFEASIBLE; //线性表不存在返回INFEASIBLE
    if (L.length == 0)     //为空返回OK否则返回ERROR
        return TRUE;
    else
        return FALSE;
}

/***************************************************************
 *函数名称：ListLength
 *函数功能： 如果线性表L存在，返回线性表L的长度，否则返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status ListLength(SqList L) {
    if (L.elem == NULL)
        return INFEASIBLE; //线性表不存在返回INFEASIBLE
    return L.length;       //否则返回线性表的长度
}

/***************************************************************
 *函数名称： GetElem
 *函数功能：如果线性表L存在，获取线性表L的第i个元素，保存在e中，返回OK；如果i不合法，返回ERROR；如果线性表L不存在，返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status GetElem(SqList L, int i, ElemType &e) {
    if (L.elem == NULL)
        return INFEASIBLE; //线性表不存在返回INFEASIBLE
    if (i > L.length || i <= 0) {
        return ERROR; //数据不合法返回ERROR
    } else
        e = L.elem[i - 1]; //否则返回第i个元素
    return OK;
}

/***************************************************************
 *函数名称： LocateElem
 *函数功能： 如果线性表L存在，查找元素e在线性表L中的位置序号并返回该序号；如果e不存在，返回0；当线性表L不存在时，返回INFEASIBLE（即-1）。
 *返回值类型：int
 ****************************************************************/
int LocateElem(SqList L, ElemType e) {
    if (L.elem == NULL) {
        return INFEASIBLE; //线性表不存在返回INFEASIBLE
    }
    int i = 0;
    for (i; i < L.length; i++) {
        if (L.elem[i] == e) {
            return i + 1; //成功找到返回该元素序号
        }
    }
    if (i == L.length)
        return 0; //未找到返回0
    return -1;
}

/***************************************************************
 *函数名称： PriorElem
 *函数功能：如果线性表L存在，获取线性表L中元素e的前驱，保存在pre中，返回OK；如果没有前驱，返回ERROR；如果线性表L不存在，返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status PriorElem(SqList L, ElemType e, ElemType &pre) {
    if (L.elem == NULL)
        return INFEASIBLE; //线性表不存在返回INFEASIBLE
    int i = 0;
    for (i; i < L.length; i++) {
        if (e == L.elem[i]) {
            if (i == 0)
                return ERROR;    //没有前驱返回ERROR
            pre = L.elem[i - 1]; //成功找到该前驱
            return OK;
        }
    }
    if (i == L.length)
        return ERROR; //未找到该元素返回ERROR
    return -1;
}

/***************************************************************
 *函数名称： NextElem
 *函数功能：如果线性表L存在，获取线性表L元素e的后继，保存在next中，返回OK；如果没有后继，返回ERROR；如果线性表L不存在，返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status NextElem(SqList L, ElemType e, ElemType &next) {
    if (L.elem == NULL)
        return INFEASIBLE; //线性表不存在返回INFEASIBLE
    int i = 0;
    for (i; i < L.length; i++) {
        if (e == L.elem[i]) {
            if (i + 1 == L.length)
                return ERROR;     //没有后继返回ERROR
            next = L.elem[i + 1]; //成功找到该后继
            return OK;
        }
    }
    if (i == L.length)
        return ERROR; //未找到该元素返回ERROR
    return -1;
}

/***************************************************************
 *函数名称： ListInsert
 *函数功能：如果线性表L存在，将元素e插入到线性表L的第i个元素之前，返回OK；当插入位置不正确时，返回ERROR；如果线性表L不存在，返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status ListInsert(SqList &L, int i, ElemType e) {
    if (L.elem == NULL)
        return INFEASIBLE; //线性表不存在返回INFEASIBLE
    if ((i <= 0 && L.length != 0) || i > L.length + 1)
        return ERROR; //数据不合法返回ERROR
    if (L.length == L.listsize) {
        SqList np;
        np.elem = (ElemType *)realloc(L.elem, sizeof(ElemType) * (L.listsize + LISTINCREMENT));
        if (np.elem == NULL)
            return OVERFLOW; //分配失败则退出
        np.length = L.length;
        np.listsize = L.listsize + LISTINCREMENT;
        L = np;
    } //若溢出则动态分配更多的空间
    int j = L.length;
    for (j; j >= i - 1; j--) {
        L.elem[j + 1] = L.elem[j];
    }                  //移动数据
    L.elem[i - 1] = e; //赋值
    L.length++;        //长度自增
    return OK;
}

/***************************************************************
 *函数名称： ListDelete
 *函数功能：如果线性表L存在，删除线性表L的第i个元素，并保存在e中，返回OK；当删除位置不正确时，返回ERROR；如果线性表L不存在，返回INFEASIBLE。// 如果线性表L存在，将元素e插入到线性表L的第i个元素之前，返回OK；当插入位置不正确时，返回ERROR；如果线性表L不存在，返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status ListDelete(SqList &L, int i, ElemType &e) {
    if (L.elem == NULL)
        return INFEASIBLE; //线性表不存在返回INFEASIBLE
    if (i <= 0 || i > L.length)
        return ERROR; //数据不合法返回ERROR
    e = L.elem[i - 1];
    int j = i - 1;
    for (j; j <= L.length; j++) {
        L.elem[j] = L.elem[j + 1];
    } //移动数据
    L.length--;
    return OK; //成功返回OK
}

/***************************************************************
 *函数名称： ListTraverse
 *函数功能：// 如果线性表L存在，依次显示线性表中的元素，每个元素间空一格，返回OK；如果线性表L不存在，返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status ListTraverse(SqList L) {
    if (L.elem == NULL)
        return INFEASIBLE; //线性表不存在返回INFEASIBLE
    int i = 0;
    for (i; i < L.length; i++) {
        printf("%d", L.elem[i]);
        if (i != L.length - 1)
            printf(" ");
    }
    printf("\n");
    return OK; //遍历成功返回OK
}

/***************************************************************
 *函数名称： SaveList
 *函数功能：如果线性表L存在，将线性表L的的元素写到FileName文件中，返回OK，否则返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status SaveList(SqList L, char FileName[]) {
    if (L.elem == NULL)
        return INFEASIBLE; //线性表不存在返回INFEASIBLE
    FILE *fp;
    fp = fopen(FileName, "w"); //打开文件
    if (fp == NULL)
        return ERROR; //打开失败返回ERROR
    for (int i = 0; i < L.length; i++) {
        fprintf(fp, "%d ", L.elem[i]);
    }
    fclose(fp); //写入文件并关闭
    return OK;
}

/***************************************************************
 *函数名称：  LoadList
 *函数功能：如果线性表L不存在，将FileName文件中的数据读入到线性表L中，返回OK，否则返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status LoadList(SqList &L, char FileName[]) {
    if (L.elem != NULL)
        DestroyList(L);
    FILE *fp;
    fp = fopen(FileName, "r"); //打开文件
    if (fp == NULL)
        return ERROR;                                               //打开失败返回ERROR
    L.elem = (ElemType *)malloc(sizeof(ElemType) * LIST_INIT_SIZE); //分配空间
    L.listsize = LIST_INIT_SIZE;
    int i = 0, tem;
    while (fscanf(fp, "%d", &L.elem[i++]) != EOF)
        ; //读入数据
    L.length = i - 1;
    fclose(fp); //关闭文件
    return OK;
}

/***************************************************************
 *函数名称：  AddList
 *函数功能：只需要在Lists中增加一个名称为ListName的空线性表，线性表数据又后台测试程序插入。
 *返回值类型：status
 ****************************************************************/
status AddList(LISTS &Lists, char ListName[]) {
    strcpy(Lists.elem[Lists.length].name, ListName);
    Lists.elem[Lists.length].L.elem = NULL;
    InitList(Lists.elem[Lists.length].L); //创建一个线性表
    Lists.length++;                       //列表长度自增
    return OK;                            //成功返回OK
}

/***************************************************************
 *函数名称：  RemoveList
 *函数功能：Lists中删除一个名称为ListName的线性表
 *返回值类型：status
 ****************************************************************/
status RemoveList(LISTS &Lists, char ListName[]) {
    if (Lists.length == 0)
        return INFEASIBLE;
    int i = 0;
    for (i = 0; i < Lists.length; i++) {
        if (!strcmp(Lists.elem[i].name, ListName)) {
            break;
        }
    }
    if (i == Lists.length)
        return ERROR;
    DestroyList(Lists.elem[i].L);
    for (i; i < Lists.length; i++) {
        strcpy(Lists.elem[i].name, Lists.elem[i + 1].name);
        Lists.elem[i].L = Lists.elem[i + 1].L;
    } //移动列表中的元素
    Lists.length--;
    return OK;
}

/***************************************************************
 *函数名称：  LocateList
 *函数功能：在Lists中查找一个名称为ListName的线性表，成功返回逻辑序号，否则返回0
 *返回值类型：int
 ****************************************************************/
int LocateList(LISTS Lists, char ListName[]) {
    if (Lists.length == 0) {
        return -1;
    }
    int i = 0;
    for (i; i < Lists.length; i++) {
        if (!strcmp(Lists.elem[i].name, ListName)) {
            break; //找到该线性表
        }
    }
    if (i == Lists.length)
        return 0; //未找到返回0
    else
        return i + 1; //成功返回序号
}

/***************************************************************
 *函数名称：  MaxSubArray
 *函数功能：初始条件是线性表L已存在且非空，请找出一个具有最大和的连续子数组（子数组最少包含一个元素），操作结果是其最大和
 *返回值类型：int
 ****************************************************************/
int MaxSubArray(SqList L) {
    if (L.elem == NULL)
        return INFEASIBLE; //线性表不存在返回INFEASIBLE
    int boundry = L.elem[0];
    int maxArray = L.elem[0];
    for (int i = 1; i < L.length; ++i) {
        if (boundry + L.elem[i] >= L.elem[i])
            boundry += L.elem[i];
        else
            boundry = L.elem[i];
        if (maxArray < boundry)
            maxArray = boundry;
    }
    return maxArray;
}

/***************************************************************
 *函数名称：  sortList
 *函数功能：初始条件是线性表L已存在；操作结果是将L由小到大排序
 *返回值类型：int
 ****************************************************************/
int sortList(SqList &L) {
    if (L.elem == NULL)
        return INFEASIBLE; //线性表不存在返回INFEASIBLE
    for (int i = 0; i < L.length; i++) {
        for (int j = 0; j < i; j++) {
            if (L.elem[j] > L.elem[i]) {
                ElemType tem = L.elem[j];
                L.elem[j] = L.elem[i];
                L.elem[i] = tem;
            }
        }
    }
    return OK; //成功返回OK
}

/***************************************************************
 *函数名称：   locate
 *函数功能：查找L在lists中的位置
 *返回值类型：status
 ****************************************************************/
status locate(SqList L, LISTS Lists) {
    if (Lists.length == 0 || L.elem == NULL) {
        return INFEASIBLE;
    }
    for (int i = 0; i < Lists.length; i++) {
        if (Lists.elem[i].L.elem == L.elem) {
            return i + 1;
        }
    }
    return ERROR;
}